%!TEX root = paper.tex

Following the notations of Section~\ref{sec:select:neg:sketch}, we
derive the bounds on $\delta(\Result, \ReSke)$ here.

First, by linearity of expectation, we have
\begin{equation*}
  \mu_j = \mathbb{E}[Z_j] = |\Result \cap P_j|,~
	\mu_Z = \mathbb{E}[Z] = |\Result|.
\end{equation*}

It is easy to see the following bound on $\delta(\Result, \ReSke)$:
\begin{equation*}
 \delta(\Result, \ReSke)
   \le 1 - \frac{\sum_j \min\{Z_j, |\Result \cap P_j|\}}
     {\max\{Z, |\Result|\}}\\
   = 1 - \frac{\sum_j \min\{Z_j, \mu_j\}}{\max\{Z, \mu_Z\}}.
\end{equation*}

By the (one-sided) Chebyshev's inequality, we have
\begin{align*}
     &\mathbf{Pr}\left[\sum_j\min\{Z_j, \mu_j\} \ge
      (1 - \Delta^-)\mu_Z\right]\\
 \ge &\mathbf{Pr}\left[\bigcap_j Z_j \ge (1 - \Delta^-)\mu_j\right] \\
 \ge &1 - \mathbf{Pr}\left[\bigcup_j Z_j \le (1 - \Delta^-)\mu_j\right] \\
 \ge &1 - \sum_j \frac{1}{1 + (\Delta^-\mu_j / \sigma_j)^2}
\end{align*}
and
\begin{align*}
     \mathbf{Pr}\left[\max\{Z, \mu_Z\} \ge (1 + \Delta^+)\mu_Z\right]
 & = \mathbf{Pr}\left[Z \ge (1 + \Delta^+)\mu_Z\right] \\
 & \le \frac{1}{1 + (\Delta^+\mu_Z / \sigma_Z)^2}.
\end{align*}
Combining the two inequalities above, we have
\begin{align*}
     &\mathbf{Pr}\left[\delta(\Result, \ReSke) \ge 1 -
      \frac{1 - \Delta^-}{1 + \Delta^+}\right] \\
%  \le &\mathbf{Pr}\left[1 - \frac{\sum_j \min\{Z_j, \mu_j\}}
%    {\max\{Z, \mu_Z\}} \ge 1 - \frac{1 - \Delta^-}{1 + \Delta^+}
%    \right]\\
 \le &\mathbf{Pr}\left[\sum_j\min\{Z_j ,\mu_j\} \le (1 - \Delta^-)\mu_Z
   \lor Z \ge (1 + \Delta^-)\mu_Z\right] \\
 \le &\sum_j \frac{1}{1 + (\Delta^-\mu_j / \sigma_j)^2} +
   \frac{1}{1 + (\Delta^+\mu_Z / \sigma_Z)^2}.
\end{align*}

To see the bounds dependent on correlation of point distribution by
objects, let $c_{ij}$ denote the number of points in partition $P_j$
that come from object $i$; i.e., $c_{ij} = |f(\R_i) \cap P_j|$, and
$C_i = \sum_j c_{ij} = |f(\R_i)|$.  It follows that $Z_j = \lambda
  \cdot \sum_i X_i c_{ij}$.  We have, for each $i$:
\begin{equation*}
 \mu_i      = \sum_j c_{ij},\quad
 \sigma_i^2 = \frac{1-p}{p} \cdot \sum_i c_{ij}^2,
\end{equation*}
and for $Z$,
\begin{equation*}
 \mu_Z      = \sum C_j,\quad
 \sigma_Z^2 = \frac{1-p}{p} \cdot \sum_i C_i^2.
\end{equation*}

For any two partitions $j$ and $j'$, the covariance and correlation
between $Z_j$ and $Z_{j'}$ are given by
\begin{equation*}
 \sigma_{jj'} = \frac{1-p}{p} \cdot \sum_i c_{ij}c_{ij'},\quad
 \rho_{jj'}   = \frac{\sigma_{jj'}}{\sigma_j\sigma_{j'}}.
\end{equation*}

The tighter bound can be obtained by taking into account the correlation
among $Z_j$'s, using the dependent multi-variate Chebyshev's
inequality as follows:
\begin{align*}
     &\mathbf{Pr}\left[\bigcap_j Z_j \ge (1 - \Delta^-)\mu_j\right] \\
 \le &1 - \frac{1}{m^2}\left(\sqrt{u} + \sqrt{m-1} \sqrt{\frac{m}
       {(\Delta^-)^2} \sum_j \frac{\sigma_j^2}{\mu_j^2} - u} \right)^2,
\end{align*}
where
\begin{align*}
 u = \frac{1}{(\Delta^-)^2} \sum_j \sum_{j'} \frac{\rho_{jj'}}
   {\mu_j \mu_{j'}}.
\end{align*}

Setting $\rho_{jj'} = 1$ for all $j$, $j'$, and we get
Ineq.~\eqref{eq:bounds-identical-distn},~\eqref{eq:bounds-identical-counts},
and~\eqref{eq:bounds-independent-distn}.

